{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "\n",
    "冒泡排序\n",
    "\n",
    "\n",
    "    比较相邻的元素。如果第一个比第二个大，就交换他们两个。\n",
    "    对第0个到第n-1个数据做同样的工作。这时，最大的数就“浮”到了数组最后的位置上。\n",
    "    针对所有的元素重复以上的步骤，除了最后一个。\n",
    "    持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 实现"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def bubble_sort(nums):\n",
    "    n = len(nums)\n",
    "    for i in range(n):\n",
    "        for j in range(1, n-i):\n",
    "            if nums[j-1] > nums[j]:\n",
    "                nums[j-1], nums[j] = nums[j], nums[j-1]\n",
    "    return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4, 5, 6, 7, 8, 9]"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [1,4,8,3,7,2,5,9,6]\n",
    "bubble_sort(nums)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 优化"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "    1、不用硬性要求一定要遍历完，如果其中某个遍历已经排好序了（没有交换），那就直接break了，用个flag记录这个状态。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def bubble_sort1(nums):\n",
    "    n = len(nums)\n",
    "    \n",
    "    for i in range(n):\n",
    "        flag = True\n",
    "        for j in range(1, n-i):\n",
    "            if nums[j-1] > nums[j]:\n",
    "                nums[j-1], nums[j] = nums[j], nums[j-1]\n",
    "                flag = False\n",
    "        if flag:\n",
    "            break\n",
    "    return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4, 5, 6, 7, 8, 9]"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [1,4,8,3,7,2,5,9,6]\n",
    "bubble_sort1(nums)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "    2、记录某次遍历时最后发生数据交换的位置，这个位置之后的数据显然已经有序，不用再排序了。因此通过记录最后发生数据交换的位置就可以确定下次循环的范围了。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def bubble_sort2(nums):\n",
    "    n = len(nums)\n",
    "    pos = 0\n",
    "    \n",
    "    for i in range(n):\n",
    "        flag = True\n",
    "        for j in range(1, pos):\n",
    "            if nums[j-1] > nums[j]:\n",
    "                nums[j-1], nums[j] = nums[j], nums[j-1]\n",
    "                flag = False\n",
    "                pos = j\n",
    "        if flag:\n",
    "            break\n",
    "    return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4, 5, 6, 7, 8, 9]"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bubble_sort2(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import timeit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "bubble_sort  0.010333899999977803 ms\n",
      "bubble_sort1 0.007230600000013965 ms\n",
      "bubble_sort2 0.0020370000000298205 ms\n"
     ]
    }
   ],
   "source": [
    "print(\"bubble_sort \",timeit.timeit(\"bubble_sort([1,4,8,3,7,2,5,9,6])\", setup=\"from __main__ import bubble_sort\", number=1000), \"ms\")\n",
    "print(\"bubble_sort1\",timeit.timeit(\"bubble_sort1([1,4,8,3,7,2,5,9,6])\", setup=\"from __main__ import bubble_sort1\", number=1000), \"ms\")\n",
    "print(\"bubble_sort2\",timeit.timeit(\"bubble_sort2([1,4,8,3,7,2,5,9,6])\", setup=\"from __main__ import bubble_sort2\", number=1000), \"ms\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "稳定或者不稳定排序的定义是，排序前后，两个相等的数字他们的顺序保持不变。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 复杂度"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$O(n^2)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"img/sort.png\">"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
